// 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

// 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

// 来源：力扣（LeetCode）
// 链接：https://leetcode-cn.com/problems/word-search
// 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

//看了题解，DFS+回溯 

// 执行用时：
// 168 ms
// , 在所有 C++ 提交中击败了
// 89.61%
// 的用户
// 内存消耗：
// 7.3 MB
// , 在所有 C++ 提交中击败了
// 31.56%
// 的用户

#include<bits/stdc++.h>
#include<string>
#include<vector>
#include<unordered_map>
#include<set>
using namespace std;

class Solution {
public:
// 传值会超时，传引用没事
    bool dfs(vector<vector<char>>& board,string& word,int index,int x,int y){
        if(board[x][y]!=word[index]){
            return false;
        }
        if(index == word.size()-1){
            return true;
        }
        char temp = board[x][y];
        board[x][y] = 0;
        if((x>0 && dfs(board,word,index+1,x-1,y)) || (y>0 &&dfs(board,word,index+1,x,y-1)) ||(y<board[0].size()-1 && dfs(board,word,index+1,x,y+1))
        || (x<board.size()-1 && dfs(board,word,index+1,x+1,y))){
            return true;
        }
        else{
            board[x][y] = temp;
        }
        return false;

    }
    bool exist(vector<vector<char>>& board, string word) {
        int h=board.size();
        int l=board[0].size();
        vector<int> pos_h;
        vector<int> pos_l;
        for(int i=0;i<h;i++){
            for(int j=0;j<l;j++){
                if(word[0]==board[i][j]){
                    pos_h.push_back(i);
                    pos_l.push_back(j);
                }
            }
        }
        if(pos_h.size()==0){
            return false;
        }
        else{
            for(int i=0;i<pos_h.size();i++){
                if(dfs(board,word,0,pos_h[i],pos_l[i])){
                    return true;
                }
            }
        }
        return false;
    }
};